package leetcode.graph.course;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 210. 课程表 II
 *
 * 学完所有课程的一个排序
 *
 */
public class FindOrder {

    // 存储有向图
    List<List<Integer>> edges;

    // 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成
    int[] visited;

    // 用数组来模拟栈，下标 n-1 为栈底，0 为栈顶
    int[] stack;
    // 栈下标
    int index;
    // 判断有向图中是否有环
    boolean valid = true;

    /**
     *
     * @param numCourses    课程数量
     * @param prerequisites 课程先后关系数组
     * @return
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 图对象初始化
        edges = new ArrayList<>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<>());
        }
        visited = new int[numCourses];

        // 栈初始化
        stack = new int[numCourses];
        // 指针指向栈底
        index = numCourses - 1;
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
        }

        // 每次挑选一个「未搜索」的节点，开始进行深度优先搜索
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        // 如果构成环, 返回空数组
        if (!valid) {
            return new int[0];
        }
        // 如果没有环，那么就有拓扑排序
        return stack;
    }

    /**
     * 深度优先遍历
     * @param courseNo  课程号
     */
    public void dfs(int courseNo) {
        // 将节点标记为「搜索中」
        visited[courseNo] = 1;

        // 搜索其相邻节点 只要发现有环，立刻停止搜索
        for (int v : edges.get(courseNo)) {
            // 如果「未搜索」那么搜索相邻节点
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            }
            // 如果「搜索中」说明找到了环
            else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        // 将节点标记为「已完成」
        visited[courseNo] = 2;
        // 将节点入栈
        stack[index] = courseNo;
        index--;
    }


    /**
     * 广度优先遍历
     *
     * @param numCourses    课程数量
     * @param prerequisites 课程表先后顺序
     * @return
     */
    public int[] findOrder2(int numCourses, int[][] prerequisites) {
        // 存储有向图
        List<List<Integer>> edges = new ArrayList<>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<>());
        }
        // 存储每个节点的入度
        int[] enters = new int[numCourses];
        // 使用数组存储节点序列
        int[] result = new int[numCourses];
        int index = 0;

        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
            // 对应节点的入度加1
            enters[info[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        // 将所有入度为 0 的节点放入队列中
        for (int i = 0; i < numCourses; ++i) {
            if (enters[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            // 从队首取出一个节点
            int u = queue.poll();
            // 放入答案中
            result[index] = u;
            index++;
            for (int v : edges.get(u)) {
                enters[v]--;
                // 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
                if (enters[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        // 队列为空, 但是结果列表的数量不是全部课程的数量, 说明构成了闭环
        if (index != numCourses) {
            return new int[0];
        }
        return result;
    }
}
